[% setvar title Higher order functions %]
<div id="archive-notice">
    <h3>This file is part of the Perl 6 Archive</h3>
    <p>To see what is currently happening visit <a href="http://www.perl6.org/">http://www.perl6.org/</a></p>
</div>
<div class='pod'>
<a name='TITLE'></a><h1>TITLE</h1>
<p>Higher order functions</p>
<a name='VERSION'></a><h1>VERSION</h1>
<pre>  Maintainer: Damian Conway &lt;<a href='mailto:damian@conway.org'>damian@conway.org</a>&gt;
  Date: 4 Aug 2000
  Last Modified: 25 Sep 2000
  Number: 23
  Version: 6
  Mailing List: <a href='mailto:perl6-language-subs@perl.org'>perl6-language-subs@perl.org</a>
  Status: Frozen
  Frozen since: v5</pre>
<a name='ABSTRACT'></a><h1>ABSTRACT</h1>
<p>This RFC proposes some syntactic sugar to simplify the creation of
higher-order functions (a.k.a. &quot;currying&quot;).</p>
<a name='DESCRIPTION'></a><h1>DESCRIPTION</h1>
<p>One situation in which the proposed Perl <code>switch</code> statement does not
provide a good substitute for a cascaded <code>if</code>, is where a switch value
needs to be tested against a series of conditions. For example:</p>
<pre>        sub beverage {
                switch (shift) {
                        case sub{ $_[0] &lt; 10 }  { return 'milk' }
                        case sub{ $_[0] &lt; 20 }  { return 'coke' }
                        case sub{ $_[0] &lt; 30 }  { return 'beer' }
                        case sub{ $_[0] &lt; 40 }  { return 'wine' }
                        case sub{ $_[0] &lt; 50 }  { return 'malt' }
                        case sub{ $_[0] &lt; 60 }  { return 'Moet' }
                        else                    { return 'milk' }
                }
        }</pre>
<p>The need to specify each condition as an anonymous subroutine is tiresome.
Each of these small subroutines is really a &quot;higher order&quot; function, which
exists merely to bind the second operand of the
<code>&lt;</code> operator.</p>
<a name='The anonymous placeholder'></a><h2>The anonymous placeholder</h2>
<p>It is proposed that Perl reserve the bareword <code>^_</code> (caret-underscore) as
a &quot;placeholder&quot; for generating higher order functions more cleanly.</p>
<p>That is, any expression containing <code>^_</code> anywhere that a value might
appear, will be converted to &quot;deferred expression&quot;: a reference to a
subroutine in which the placeholders are replaced by the appropriate
number and sequence of scalar arguments.</p>
<p>That is, the expression:</p>
<pre>        $check = ^_ == ^_**2 *^_ or die ^_;</pre>
<p>is equivalent to:</p>
<pre>        $check = sub (;$$$$) {
            $_[0] == $_[1]**2 *$_[2] or die $_[3]
        };</pre>
<p>This could then be invoked:</p>
<pre>        $check-&gt;(@args);
        </pre>
<p>It would also be possible to interpolate an argument list into a static
expression like so:</p>
<pre>        (^_ == ^_**2 *^_ or die ^_)-&gt;(@args);</pre>
<a name='Named placeholders'></a><h2>Named placeholders</h2>
<p>Those not currently studying or using geometry might not be too sure what
they're dealing with when they see:</p>
<pre>        $check = ^_ == ^_**2 *^_ or die ^_;</pre>
<p>in a program. However, the following is self-documenting:</p>
<pre>        $check = ^cylinder_vol == ^radius**2 * ^height
          or die ^last_words;</pre>
<p>This uses the <i>named placeholder</i> notation. If two placeholders use the
same identifier, they refer to the same argument. Therefore, the following
is equivalent to the previous line:</p>
<pre>        $check = ^cylinder_vol == ^radius*^radius * ^height
          or die ^last_words;</pre>
<a name='Positional placeholders'></a><h2>Positional placeholders</h2>
<p>The order in which the arguments appear in a function may not be
convenient:</p>
<pre>        # getMeasurements returns ($height, $radius)
        @measurements = getMeasurementsFromSomeplace();
        $check-&gt;($volume, reverse(@measurements), 'Invalid measurements');</pre>
<p>A convenient way around this is using <i>positional placeholders</i>:</p>
<pre>        $check = ^2 == ^0**2 * ^1 or die ^3;
        @measurements = getMeasurementsFromSomeplace();
        $check-&gt;(@measurements, $volume, 'Invalid measurements');</pre>
<p>The numbers after the <code>^</code> prefix correspond directly to the indices
of the correpsonding elements of @_.</p>
<p>Positional placeholders can be used to re-order named placeholders too:</p>
<pre>        $check = ^cylinder_vol == ^radius**2 * ^height
          or die ^last_words;
        $check2 = $check-&gt;(^2, ^0, ^1, ^3);</pre>
<a name='Choice of notation'></a><h2>Choice of notation</h2>
<p>The placeholder notation has been chosen to be consistent with the
existing Perl scalar access notation (but using a ^ prefix rather than a $).
In particular, the &quot;numeric&quot; placeholders: ^0, ^1, ^2, etc. represent
$_[0], $_[1], $_[2], etc.</p>
<p>There is a minority that believes that these numerical placeholders
should start at ^1 (representing $_[0]). They feel that the analogy to
$1, $2, $3 is stronger than the logical association of $_[0], $_[1],
$_[2]. The author (along with many others) is <i>vehemently</i> opposed to
this suggestion, but includes it for completeness.</p>
<a name='Combining placeholder types'></a><h2>Combining placeholder types</h2>
<p>Although not necessarily a good idea, these can be mixed in a single
higher-order function:</p>
<pre>        $icky_func = ^test ? ^1 * ^_ : ^2 * ^_;</pre>
<p>First the positional placeholders are filled in (a higher numbered
positional placeholder than the number of parameters results in a
compile-time error). The anonymous and named placeholders fill in the
missing places in the order in which they appear, from left to right.</p>
<p>However, for the good of international mental health, users should be
encouraged to consider using a consistent approach within a single
higher-order function definition.</p>
<a name='Examples:'></a><h2>Examples:</h2>
<p>With <code>^_</code>, the previous ugly case statements can be rewritten:</p>
<pre>        sub beverage {
                switch (shift) {
                        case  ^_ &lt; 10  { return 'milk' }
                        case  ^_ &lt; 20  { return 'coke' }
                        case  ^_ &lt; 30  { return 'beer' }
                        case  ^_ &lt; 40  { return 'wine' }
                        case  ^_ &lt; 50  { return 'malt' }
                        case  ^_ &lt; 60  { return 'Moet' }
                        else           { return 'milk' }
                }
        }</pre>
<p>Likewise a Tree class might provide a traversal callback like so:</p>
<pre>        $root = Tree-&gt;new(load_from =&gt; &quot;datafile&quot;)

        my $sum = 0;
        $root-&gt;traverse( $sum += ^_ );</pre>
<p>Higher order functions would also be very useful with the proposed
<code>reduce</code> function:</p>
<pre>        $sum  = reduce ^_+^_ (0,@vals);
        $prod = reduce ^_*^_ (1,@vals);</pre>
<p>and with the new (5.6) semantics of <code>sort</code>:</p>
<pre>        @sorted = sort(^_ &lt;=&gt; ^_, @list);</pre>
<p>Better yet, since the generated subroutine has named arguments whenever named
placeholders are used, the following also works as expected:</p>
<pre>        @reverse_sorted = sort(^b &lt;=&gt; ^a, @list);</pre>
<p>(It is proposed that C,sort&gt; should name arguments passed to its comparator
subroutine <code>a:</code> and &lt;b:&gt;, in that order to make this possible).</p>
<a name='Re-currying deferred expressions'></a><h2>Re-currying deferred expressions</h2>
<p>The subroutines generated by a placeholder are not exactly like the
equivalent subroutines shown above. If they are called with fewer than the
required number of arguments, they return another higher order function,
which now has the specified arguments bound as well.</p>
<p>Thus:</p>
<pre>        $check_or_die = $check-&gt;(@args[0..2]);</pre>
<p>produces another deferred expression, one that requires only a
single argument:</p>
<pre>        $check_or_die-&gt;(&quot;Error message&quot;);</pre>
<p>Arguments can also be bound by the explicit use of placeholders. This
allows arguments other than the last to be bound as well:</p>
<pre>        $check_n = $check-&gt;(^_, @args[1..3]);

        # and later...

        $check_n-&gt;($n);</pre>
<p>Thus the expression:</p>
<pre>        $check = ^_ == ^_**2 *^_ or die ^_;</pre>
<p>is actually equivalent to:</p>
<pre>        $check = sub (;$$$$) {
                  @_==0 ?  ^_ == ^_**2 *^_ or die ^_
                : @_==1 ?  $_[0] == ^_**2 *^_ or die ^_
                : @_==2 ?  $_[0] == $_[1]**2 *^_ or die ^_
                : @_==3 ?  $_[0] == $_[1]**2 *$_[2] or die ^_
                :          $_[0] == $_[1]**2 *$_[2] or die $_[3]
                ;
        };</pre>
<p>Note that the level of currying for a deferred expression can always be
determined by looking at its prototype.</p>
<a name='Extent of curried expressions'></a><h2>Extent of curried expressions</h2>
<p>Suppose a tree class implements a traverse
method that walks through the nodes in the tree.
Then the desired behaviour of:</p>
<pre>        $root = Tree-&gt;new();

        # and later...

        $root-&gt;traverse( $sum += ^_ );</pre>
<p>is clearly:</p>
<pre>        $root-&gt;traverse( sub { $sum += $_[0] } );</pre>
<p>and not:</p>
<pre>        sub { $root-&gt;traverse( $sum += $_[0] ); }</pre>
<p>Since either is a plausible interpretation, some rules are required to
ensure that Perl always DWIMs with higher-order functions.
There is one general principle and six 'halting rules' for currying.</p>
<p>When Perl sees an expression containing a placeholder, it creates a
curried expression around this placeholder that is as large as possible,
stopping when it reaches a halting rule. In an expression containing
multiple placeholders, the placeholders are only combined into a single
curried expression where there is no halting rule between them.</p>
<p>The following rules are proposed:</p>
<ul>
<li><a name='Pure assignment'></a>Pure assignment</li>
<p>Currying halts at a pure assignment (i.e. '='), but not at any
other assignment variant (e.g. +=, ||=). Otherwise:</p>
<pre>        $check = ^_ == ^_**2 *^_ or die ^_;</pre>
<p>would be interpreted as:</p>
<pre>        sub {$check = $_[0] == $_[1]**2 *$_[2] or die $_[3]};</pre>
<p>which is not WIM.</p>
<li><a name='Sub called in void context'></a>Sub called in void context</li>
<p>Currying halts in the argument list of a subroutine (or method) that is
called in a void context. The tree traversal example given above shows a
method in a void context (any return value from $root-&gt;traverse is being
ignored). Therefore just its argument is curried, rather than the whole
call expression.</p>
<li><a name='Control expression'></a>Control expression</li>
<p>Within a flow control statement (e.g. switch) currying halts within the
control expression. For instance:</p>
<pre>        switch ($val) {
                case ^_&lt;9 {print &quot;That's a little number&quot;};
        }</pre>
<p>expands to:</p>
<pre>        switch ($val) {
                case sub{$_[0]&lt;9} {print &quot;That's a little number&quot;};
        }</pre>
<p>because ^_&lt;9 appears in the control expression of the switch statement.</p>
<li><a name='Explicit curry nonpropagation context'></a>Explicit curry nonpropagation context</li>
<p>A prototype modifier <code>^</code> is proposed. It would allow functions to indicate
that one or more of their arguments should <i>not</i> propogate currying. This
would allow functions to return a value and still Do The Right Thing with
placeholders. Hence:</p>
<pre>        sub traverse ($^) { ...  }

        $num_nodes = traverse( $root, $sum += ^_ );</pre>
<p>means:</p>
<pre>        $num_nodes = traverse( $root, sub{$sum += $_[0]} );</pre>
<p>not:</p>
<pre>        $num_nodes = sub{ traverse( $root, $sum += $_[0] ) };</pre>
<p>Whereas:</p>
<pre>        $num_nodes = traverse( ^_ , $sum += ^_ );</pre>
<p>means:</p>
<pre>        $num_nodes = sub { traverse( $_[0], sub{$sum += $_[0]} ) };</pre>
<p>Note that in this last example, the first argument curried the entire
call to traverse, whilst the ^ prototype on the second argument caused
its curry to be handled separately.</p>
<li><a name='Implicit curry nonpropagation context'></a>Implicit curry nonpropagation context</li>
<p>Subroutine arguments prototyped as <code>&amp;</code> would not propagate the currying
of their arguments. For example:</p>
<pre>        sub mymap (&amp;@) { ... }

        @mapped = mymap ^_+1, @unmapped;</pre>
<p>would be equivalent to:</p>
<pre>        @mapped = mymap sub{$_[0]+1}, @unmapped;</pre>
<p>not:</p>
<pre>        @mapped = sub { mymap {$_[0]+1}, @unmapped; }</pre>
<p>Note that this rule also covers the following built-in functions:
<code>map</code>, <code>grep</code>, <code>sort</code>, <code>reduce</code>, <code>zip</code>.</p>
</ul>
<a name='Resolving ambiguity'></a><h2>Resolving ambiguity</h2>
<p>The following is ambiguous:</p>
<pre>        $check_start = $somestring =~ /^_foobar/; </pre>
<p>This should be interpreted as an immediate pattern match for '_foobar' at
the start of a string. To cause this to be interpreted as a higher order
function, the ambiguity must be resolved through using braces:</p>
<pre>        $check_start = $somestring =~ /^{_}foobar/;</pre>
<p>which creates a higher order function testing for its argument, followed
by 'foobar', anywhere in $somestring. That is:</p>
<pre>        $check_start = sub { $somestring =~ /$_[0]foobar/ };</pre>
<a name='IMPLEMENTATION'></a><h1>IMPLEMENTATION</h1>
<p>Probably a pragma:</p>
<pre>        use higher;</pre>
<p>Implementation of the 'higher' pragma is left as an exercise to the
reader ;-)</p>
<a name='SEE ALSO'></a><h1>SEE ALSO</h1>
<p>RFC 22: Builtin switch statement</p>
<p>RFC 76: Builtin: reduce</p>
<p>RFC 128: Subroutines: Extend subroutine contexts to include named parameters and lazy arguments</p>
<a name='REFERENCES'></a><h1>REFERENCES</h1>
<a name='Higher-order functions and currying'></a><h2>Higher-order functions and currying</h2>
<p>A quick introduction:
<a href='http://www.tunes.org/~iepos/introduction-to-logic/chap00/sect00.html' target='_blank'>www.tunes.org</a></p>
<p>Definition of currying: <a href='http://www.cs.nott.ac.uk/~gmh//faq.html' target='_blank'>www.cs.nott.ac.uk</a>#currying</p>
<p>Implementation in Haskell: <a href='http://www.haskell.org/tutorial/functions.html' target='_blank'>www.haskell.org</a></p>
</div>
